DAY 30 試題

問題描述

給定一個由字串組成的陣列 strs，要求將其中的異位詞（Anagrams）分組。你可以以任意順序返回分組結果。

範例 1：

• 輸入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
• 輸出：[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
• 解釋：
  • 字串 "nat" 和 "tan" 是異位詞，因為它們可以透過重排彼此形成對方。
  • 字串 "ate", "eat" 和 "tea" 也是異位詞，它們可以互相重排成對方。
  • 字串 "bat" 沒有與其他字串組成異位詞。

範例 2：

• 輸入：strs = [""]
• 輸出：[[""]]

範例 3：

• 輸入：strs = ["a"]
• 輸出：[["a"]]

限制條件：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 只包含小寫英文字母。

解題思路

異位詞（Anagrams）指的是由相同字母組成的不同排列組合。換句話說，如果兩個字串由完全相同的字母組成，且每個字母的數量一致，那麼這兩個字串就是異位詞。因此，可以根據每個字串的排序後結果作為鑑別異位詞的標準。
解題步驟：

1. 排序字母：對於每個字串，將其字母進行排序，排序後的結果就是鑑別異位詞的關鍵。異位詞在排序後的字母順序必然相同。
2. 將異位詞分組：我們可以使用一個 hash map，鍵為排序後的字母結果，值為這些異位詞的原始字串組成的列表。這樣相同鍵的字串就是異位詞，將它們分組存放到同一個列表中。
3. 輸出結果：將 hash map 中的值，也就是異位詞的分組，輸出即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagramGroups;
        
        // 將每個字串按字母順序排序後，存入對應的異位詞群組
        for (string s : strs) {
            string sortedStr = s;
            sort(sortedStr.begin(), sortedStr.end());
            anagramGroups[sortedStr].push_back(s);
        }
        
        // 將hash map中的值(每個異位詞群組)轉換為結果形式
        vector<vector<string>> result;
        for (auto& group : anagramGroups) {
            result.push_back(group.second);
        }
        
        return result;
    }
};

解法重點與分析

1. 排序字串：每個字串透過字母排序，能將異位詞轉換為相同的形式，例如 "eat", "tea" 和 "ate" 經排序後都變成 "aet"，這樣可以簡單地識別哪些字串是異位詞。
2. 使用 hash map 分組：我們利用 unordered_map，其鍵是排序後的字串，值是原始字串列表，這樣相同鍵的字串會自動歸為一組。
3. 時間複雜度：排序每個字串的時間複雜度為 O(k log k)，其中 k 是字串的長度。因此，對於 n 個字串，每個字串長度平均為 k，總時間複雜度為 O(n * k log k)。
4. 空間複雜度：使用的額外空間主要來自 hash map，存儲了所有字串的分組結果，空間複雜度為 O(n * k)，其中 n 是字串數量，k 是字串的平均長度。

總結

這道題利用異位詞排序後具有相同形式的特性來進行分組。透過 hash map 我們能高效地將異位詞進行分組，這個解法的時間和空間複雜度都適合處理大規模的輸入數據。在面對異位詞這類問題時，排序字串並進行 hash 是一種經典的技巧。

以上是第三十天的自學內容分享，也就是最後一天的鐵人賽了。
感謝這段時間大家的觀看，謝謝大家。